package video.simple100;


import org.junit.Test;

/***
 *  108. 将有序数组转换为二叉搜索树
 */
public class LeetCode108 {


    @Test
    public void test() {
        int[] nums = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        sortedArrayToBST(nums);
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return nextNode(nums, 0, nums.length - 1);
    }


    /**
     *
     * @author wangsong
     * @param nums  原始数据
     * @param l 左边界
     * @param f 右边界
     * @date 2022/4/6 0006 21:37
     * @return video.simple100.LeetCode108.TreeNode
     * @version 1.0.0
     */
    TreeNode nextNode(int[] nums, int l, int f) {
        if (l > f) {
            return null;
        }
        // 1、计算中间值(索引)
        int mid = l + (f - l) / 2;
        // 2、构建当前节点
        TreeNode node = new TreeNode(nums[mid]);
        // 3、递归左节点
        node.left = nextNode(nums, l, mid - 1);
        // 4、递归右节点
        node.right = nextNode(nums, mid + 1, f);
        return node;
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
//
//    给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
//
//        高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
//
//         
//
//        示例 1：
//
//
//        输入：nums = [-10,-3,0,5,9]
//        输出：[0,-3,9,-10,null,5]
//        解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
//
//        示例 2：
//
//
//        输入：nums = [1,3]
//        输出：[3,1]
//        解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
//         
//
//        提示：
//
//        1 <= nums.length <= 104
//        -104 <= nums[i] <= 104
//        nums 按 严格递增 顺序排列
//
//        来源：力扣（LeetCode）
//        链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
//        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。